import java.util.Map;
import java.util.HashMap;
import java.util.StringTokenizer;

public class PriorityQueue {
	int counter;
	RandomStringGenerator randomStringGenerator;
	Node[] nodeArray;
	int nodeArraySize;
	Map<String, Integer> characterFrequency; 
	Map<String, String> characterEncoding;

	public PriorityQueue(RandomStringGenerator randomStringGenerator) {
		counter = 0;
		this.randomStringGenerator = randomStringGenerator;
		characterFrequency = new HashMap<String, Integer>(); 
		characterEncoding = new <String, String>HashMap();
		initializeCharacterMap();
	}
	
	public void initializeCharacterMap() {
		int i = 0;
		while(i < randomStringGenerator.alphabet.length){
			characterFrequency.put(randomStringGenerator.alphabet[i], 0);
			i++;
		}
	}
	public void mapChacterToFrequency(String randomString, String delimiter) {
		StringTokenizer stringTokenizer = new StringTokenizer(randomString,delimiter);
		while(stringTokenizer.hasMoreTokens()){
			String key = stringTokenizer.nextElement().toString(); 
			int value = characterFrequency.get(key) + 1;
			characterFrequency.put(key, value);
		}
	}
		
	public void initializePriorityQueue() {
		nodeArraySize = randomStringGenerator.alphabet.length;
		this.nodeArray = new Node[nodeArraySize];
		int i = 0;
		while(i < nodeArraySize){
			counter++;
			String characterString = randomStringGenerator.alphabet[i];
			int frequency = characterFrequency.get(characterString);
			nodeArray[i] = new Node(characterString, frequency);
			i++;
		}
	}
	
	public void  buildMinHeap() {
		for (int i = ((this.nodeArraySize) / 2); i >= 0; i--){
			minHeapify(i);
		}
	}
	
	public void minHeapify(int index){
		int lIndex = left(index);
		int rIndex = right(index);
		int smallestIndex;
		if ((lIndex < this.nodeArraySize) && (this.nodeArray[lIndex].frequency < this.nodeArray[index].frequency)) {
			smallestIndex = lIndex;
			counter++;
		} else {
			smallestIndex = index;
			counter++;
		}
		if ((rIndex < this.nodeArraySize) && (this.nodeArray[rIndex].frequency< this.nodeArray[smallestIndex].frequency)) {
			smallestIndex = rIndex;
			counter++;
		}
		if (smallestIndex != index) {
			
			Node tempNode = this.nodeArray[index];
			counter++;
			this.nodeArray[index] = this.nodeArray[smallestIndex];
			counter++;
			this.nodeArray[smallestIndex] = tempNode;
			minHeapify(smallestIndex);
			counter++;
		}
	}
	
	public Node extractNode() {
		if(this.nodeArraySize < 1){
			counter++;
			return null;
		}
		Node min = this.nodeArray[0];
		counter++;
		this.nodeArray[0] = this.nodeArray[(nodeArraySize - 1)];	
		counter++;
		this.nodeArraySize--;
		counter++;
		this.minHeapify(0);
		counter++;
		return min;	
	}
	
	public void insertNode(Node node){
		nodeArraySize++;
		counter++;
		nodeArray[(nodeArraySize-1)] = null;
		counter++;
		decreaseKey(node, (nodeArraySize-1));
		counter++;
	}
	
	public void decreaseKey(Node node, int index){
		nodeArray[index] = node;
		counter++;
		while(index >= 0 && nodeArray[parent(index)].frequency > nodeArray[index].frequency ){
			Node tempNode  = nodeArray[index];
			counter++;
			nodeArray[index] = nodeArray[parent(index)];
			counter++;
			nodeArray[parent(index)] = tempNode;
			counter++;
			index = parent(index);
		}
	}
	
	public void huffmanEncoder(String randomString){
		mapChacterToFrequency(randomString, randomStringGenerator.delimiter);
		initializePriorityQueue();
		buildMinHeap();
		for(int i = 0; i < nodeArray.length-1; i++){
			Node node = new Node();
			counter++;
			node.left = this.extractNode();
			counter++;
			node.right = this.extractNode();
			counter++;
			node.frequency = node.left.frequency + node.right.frequency;
			this.insertNode(node);
			counter++;
		}
		System.out.println("\n\n HuffmanEncoding Tree\n");
		displayHuffmanEncodingTree(nodeArray[0], "");
		System.out.println("Here is the huffman encoding for the random string " + randomString +":\n\n\n");
		System.out.println("HuffmanEncoding: " + convertStringToHuffmanEncoding(randomStringGenerator.randomString) +"\n\n\n");
		System.out.println("The number of operations for input size of " + randomStringGenerator.alphabet.length + " took " + counter + " atomic operations ");
	}
	
	//Displaying the huffman tree using DFS
	public String displayHuffmanEncodingTree(Node node, String encoding) {
		StringBuilder stringBuilder = new StringBuilder(encoding);
		if(node.left == null){
			System.out.println("The encoding for the unique character " + node.characterString + " which had a fequency of " + node.frequency + " is " + stringBuilder.toString());
			characterEncoding.put(node.characterString, stringBuilder.toString());
			counter++;
			return stringBuilder.toString();
		}
		else if (node.right == null){
			System.out.println("The encoding for the unique character " + node.characterString + " which had a frequency of " + node.frequency + " is " + stringBuilder.toString());
			characterEncoding.put(node.characterString, stringBuilder.toString());
			counter++;
			return stringBuilder.toString();
		}
		else{
				Node nodeLeft = node.left;
				counter++;
				stringBuilder.append("0");
				stringBuilder = new StringBuilder(displayHuffmanEncodingTree(nodeLeft, stringBuilder.toString()));
				stringBuilder.deleteCharAt(stringBuilder.length()-1);
				
				Node nodeRight = node.right;
				counter++;
				stringBuilder.append("1");
				stringBuilder = new StringBuilder(displayHuffmanEncodingTree(nodeRight,stringBuilder.toString()));	
				stringBuilder.deleteCharAt(stringBuilder.length()-1);	
		}
		return stringBuilder.toString();
	}
	
	
	public String convertStringToHuffmanEncoding(String randomString) {
		StringBuilder stringBuilder = new StringBuilder();
		StringTokenizer stringTokenizer = new StringTokenizer(randomString, randomStringGenerator.delimiter );
		while(stringTokenizer.hasMoreTokens()){
			counter++;
			String key = stringTokenizer.nextElement().toString();
			stringBuilder.append(characterEncoding.get(key));
			stringBuilder.append("\n");
		}
		stringBuilder.append("end");
		return stringBuilder.toString();
	}
	
	public int left(int index){
		return (2 * index + 1);	
	}
	
	public int right(int index) {
		return (2 * index + 2);
	}
	
	public int parent(int index){
		return ((index - 1) / 2);
	}
}
